Some Aspects Of Graph Coloring

Graph coloring is a central topic in graph theory,and various coloring concepts have been studied in the literature.This thesis studies some of the coloring concepts and related problems.These include coloring of generalized signed graphs,strong fractional choice number of graphs,generalized coloring number of graphs,twin-width of graphs,(combinatorial)discrepancy of definable set systems and χp-bounded classes of graphs.A signed graph is a pair(G,σ),where G is a graph and σ:E(G)→{+,-} is a signature which assigns to each edge e a sign σ(e)∈ {+,-}.In a coloring of signed graphs,the sign σ(e)determines the pairs of colors that need to be avoided as the colors of the end vertices of e.A generalized signed graph is also a pair(G,σ),where the signs is a set S of permutations,and the signature σ assigns to each edge e a permutationσ(e)∈S as its sign.In a coloring f of a generalized signed graph(G,σ),the sign σ(e)determines the pairs of colors that need to be avoided as the colors of the end vertices of e=xy,namely f(y)≠σ(e)(f(x)).Let Sk be the set of all permutations of[k].A natural question motivated by the Four Color Theorem is for which subsets S of S4,every planar graph is S-4-colorable?This question is now completely answered:only S={id} has this property,which means that the Four Color Theorem is tight in the sense of generalized signed graph coloring.This answer is obtained in a sequence of five papers,by different groups of authors.The contribution of this thesis is the results in one of the papers,which shows that many sets S do not have the desired property.The thesis also consider the questions for which subsets S of S3,every triangle-free planar graph is S-3-colorable.This question can be viewed as exploring the tightness of Gr(?)tzsch Theorem.Our result shows that Grotzsch Theorem is almost tight,but the whole question is not completely answered yet.We prove that for any subset S of S3,if S is not conjugate to a subset of{id,(12)},then there exists a triangle-free planar graph which is not S-3-colorable.Another attempt to strengthen Grotzsch Theorem is to consider multiple list coloring of triangle-free planar graphs.It was proved by Voigt that there are triangle-free planar graphs that are not 3-choosable.This thesis strengthens Voigt’s result by considering the strong fractional choice number of graphs and proves that the supremum of the strong fractional choice number of triangle-free planar graphs is at least 3+1/17.One important subject in structural graph theory is to study the structural complexity of graphs or classes of graphs.If restricted to some classes of graphs with simple structures,many problems that are NP-complete for general graphs could have polynomial algorithms.In this spirit,a few concepts and graph invariants are studied extensively in the literature.These include tree-width of graphs,tree-depth of graphs,generalized coloring number,etc.Recently,the concept of twin-width was introduced by Bonnet,Kim,Thomassé and Watrigant in[8].In this thesis,we study the relation between twin-width and generalized coloring number.We prove that a graph G with no Ks,s-subgraph and twin-width d has strong(weak)r-coloring numbers bounded by an exponential function of r and that we can construct graphs achieving such a dependency in r.One of the two central notions in structural theory of classes of sparse graphs is the classes with bounded expansion.These classes have strong algorithmic and structural properties.and enjoy numerous characterizations and applications.In this thesis,we study discrepancy of graph classes with bounded expansion.Discrepancy theory emerged from the study of the irregularities of statistical distributions and number sequences.Combinatorial discrepancy is a significant subject in its own right in this area.It measures the inevitable irregularities of set systems and the inherent difficulty to approximate them.We give a new characterization of bounded expansion classes in terms of discrepancy of definable set systems.In particular,we prove that the maximum discrepancy over all subgraphs H of a graph G of the neighborhood set system of H belongs to both Ω(logdeg(G))and O(deg(G)),where deg(G)denotes the degeneracy of G.We extend this result to inequalities relating weak coloring numbers and discrepancy of graph powers;we derive a new characterization of bounded expansion classes.The notion of χ-boundedness is a central topic in chromatic graph theory.This thesis studies χ-bounded classes in the context of star colorings and,more generally,χpcolorings,say χs-bounded and(strongly and weakly)χp-bounded classes.This fits to a general scheme of sparsity and leads to natural extensions of the notion of bounded expansion class.Here we solve two conjectures related to star coloring(i.e.χ2)boundedness.One of the conjectures asserts that for any tree T,the class of all(T,C4)-free graphs is χs-bounded.We prove that for any forset T,the class of all(T,Kr,t)-free graphs is χs-bounded if and only if r=1 or T is a subgraph of the 1-subdivision of a tree.Hence the conjecture is refuted,but a weaker version holds.We give strutural characterizations of strongly χp-bounded classes(for every integer p)in terms of bounded expansion,in terms of topological minors and in terms of restricted dualities.And we give structural characterizations of weakly χp-bounded classes(for every integer p)in terms of topological minors,etc.We also generalize a result of Wood relating the chromatic number of a graph to the star chromatic number of its 1-subdivision.