The Monochromatic Connectedness Of Graphs

In recent years,the connection coloring problem of graphs has developed vig-orously.The connection coloring problem is the study of the connectedness of an edge-colored graph,such as:rainbow connection coloring,proper connection color-ing,monochromatic connection coloring and conflict-free coloring.As we know that there are two ways to study the edge-connectivity of a graph,one way is by using paths and the other is by using edge-cuts.The above four types of connection coloring are all study connectedness of graphs by using paths.In 2018,Chartrand et al.proposed the concept rainbow disconnection colorings of graphs,which study rainbow connected-ness by using rainbow edge-cuts.We mainly study the monochromatic connectedness of graphs in this thesis.The main content of this thesis is divided into two parts:in the first part(Chapter 2 and Chapter 3),we generalize the concept monochromatic con-nection coloring and study them;in the second part(from Chapter 4 to Chapter 7),we study monochromatic disconnection colorings of graphs.In fact,we study monochro-matic connectedness by using monochromatic paths and monochromatic edge-cuts in these two parts,respectively.For an edge-colored graph,a path(an edge-cut)is called a monochromatic path(a monochromatic edge-cut)if all edges of the path(the edge-cut)are colored with the same color.Caro et al.proposed the concept monochromatic connection colorings of graphs.An edge-coloring of a graph is called a monochromatic connection coloring if any two vertices are connected by a monochromatic path.In this thesis,we first generalize the concept monochromatic connection coloring in three ways:for an edge-colored graph G,if any two vertices are connected by k edge-disjoint monochromat-ic paths,then we call the edge-coloring a monochromatic k-edge-connection coloring(or MCk-coloring for short)of G;if any two vertices are connected by k edge-disjoint monochromatic paths and the colors of these paths are pairwise differently,then we call the edge-coloring a rainbow monochromatic k-edge-connection coloring(or RMCk-coloring for short)of G;if any two vertices are connected by k edge-disjoint monochro-matic paths and these paths are colored with the same color,then we call the edge-coloring a uniformly monochromatic k-edge-connection coloring(or UMCk-coloring for short)of G.The MCk-number(RMCk-numbery,UMCk-number)of G,denoted by mck(G)(rmck(G),umck(G)),is the maximum number of colors that are allowed in or-der to make G have an MCk-coloring(an RMCk-coloring,a UMCk-coloring).Secondly,we talk about monochromatic disconnection colorings of graphs.For an edge-colored graph G,if any two vertices are separated by a monochromatic edge-cut(the two ver-tices are in different components when deleting the monochromatic edge-cut),then we call the edge-coloring a monochromatic disconnection coloring of G(or MD-coloring for short).The MD-number of G,denoted by md(G),is the maximum number of colors that are allowed in order to make G have an MD-coloring.In Chapter 1,we introduce the fundamental definitions and notation.We also list several known results and then introduce an overview of our main results of this thesis.In Chapter 2,we study monochromatic k-edge-connection colorings and uniformly monochromatic k-edge-connection colorings of graphs.We first give a conjecture about MCk-number,and verify that the conjecture is true when k=2.We also prove that the conjecture is true for some special graphs.Secondly,we give a relationship between the UMCk-number of a graph and its minimum k-edge-connected spanning subgraphs.In Chapter 3,we study rainbow monochromatic k-edge-connection colorings of graphs.We first give a necessary and sufficient condition for the existence of RMCk-colorings.Secondly,we give some sufficient conditions for a graph whose RMCk-number reaches the lower bound.At last,we talk about sharp threshold function for RMCk-number.In Chapter 4,we introduce some basic results for monochromatic disconnection coloring,which are useful for the following proofs.In addition,we give some graphs with MD-number one,and then prove that almost all graphs have MD-number one.In Chapter 5,we study the monochromatic disconnection colorings of four types of graph products(Cartesian product,strong product,lexicographic product and tensor product)and line graphs.In Chapter 6,we study two extremal problems of monochromatic disconnection coloring:Nordhaus-Gaddum-type problem and Erdos-Gallai-type problem.In Chapter 7,we propose a conjecture that md(G)?[|C|/k]for any k-connected graph,and verify that the conjecture is true for k=1,2 and k?[|G|/2|.We study graphs with diameter 2 and characterize the extremal graphs of k-connected graphs when k=2 and k?[|G|/2].in addition.we give two upper bounds of the MD-number of a graph G,one of which depends on the connectivity of G,and the other depends on the independent number of G.In Chapter 8,we put forward some problems for further study.