Minimum order of graphs with given coloring parameters

DOI10.1016/J.DISC.2014.12.002MaRDI QIDQ488290zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Gábor Bacsó, Piotr Borowiecki, Mihály Hujter, Zsolt Tuza

Publication date 23 January 2015

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1312.7522

zbMATH Keywords

greedy algorithmbipartite graphgraph coloringextremal graphGrundy numberachromatic number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Extremal problems in graph theory (05C35) Coloring of graphs and hypergraphs (05C15)

Abstract: A complete $k$-coloring of a graph $G=(V,E)$ is an assignment $varphi:Vo1,ldots,k$ of colors to the vertices such that no two vertices of the same color are adjacent, and the union of any two color classes contains at least one edge. Three extensively investigated graph invariants related to complete colorings are the minimum and maximum number of colors in a complete coloring (chromatic number $chi(G)$ and achromatic number $psi(G)$, respectively), and the Grundy number $Gamma(G)$ defined as the largest $k$ admitting a complete coloring $varphi$ with exactly $k$ colors such that every vertex $vinV$ of color $varphi(v)$ has a neighbor of color $i$ for all $1lei<varphi(v)$. The inequality chain $chi(G)leGamma(G)lepsi(G)$ obviously holds for all graphs $G$. A triple $(f,g,h)$ of positive integers at least 2 is called realizable if there exists a connected graph $G$ with $chi(G)=f$, $Gamma(G)=g$, and $psi(G)=h$. Chartrand et al. (A note on graphs with prescribed complete coloring numbers, J. Combin. Math. Combin. Comput. LXXIII (2010) 77-84) found the list of realizable triples. In this paper we determine the minimum number of vertices in a connected graph with chromatic number $f$, Grundy number $g$, and achromatic number $h$, for all realizable triples $(f,g,h)$ of integers. Furthermore, for $f=g=3$ we describe the (two) extremal graphs for each $hgeq6$. For $h=4$ and $5$, there are more extremal graphs, their description is contained as well.

Recommendations

• A note on graphs with prescribed complete coloring numbers
• A four colorings theorem
• scientific article; zbMATH DE number 4053646
• Results on the Grundy chromatic number of graphs
• Grundy numbers of products of paths, cycles, and stars

Cites work

• scientific article; zbMATH DE number 1088659 (Why is no real title available?)
• scientific article; zbMATH DE number 2147949 (Why is no real title available?)
• scientific article; zbMATH DE number 3800939 (Why is no real title available?)
• scientific article; zbMATH DE number 3298599 (Why is no real title available?)
• A lower bound for approximating the Grundy number
• A note on graphs with prescribed complete coloring numbers
• Achromatic number is NP-complete for cographs and interval graphs
• Algorithms for Vertex Partitioning Problems on Partial k-Trees
• Approximating the achromatic number problem on bipartite graphs
• Approximation algorithms for the achromatic number.
• Dynamic coloring of graphs
• Edge Dominating Sets in Graphs
• Further results on the achromatic number
• Graph Colorings
• Graph with given achromatic number
• Grundy number and products of graphs
• Inequalities for the Grundy chromatic number of graphs
• New bounds for the chromatic number of graphs
• On approximating the achromatic number
• On the Grundy number of a graph
• On the pseudoachromatic number of a graph
• On-line 3-chromatic graphs. II: Critical graphs
• On-line coloring \(k\)-colorable graphs
• Some perfect coloring properties of graphs
• The complexity of harmonious colouring for trees

Cited in

(9)

• A four colorings theorem
• Minimal colorings for properly colored subgraphs
• A note on graphs with prescribed complete coloring numbers
• Graphs with least number of colorings
• scientific article; zbMATH DE number 3205929 (Why is no real title available?)
• scientific article; zbMATH DE number 861338 (Why is no real title available?)
• Minimax relations for the partial q-colorings of a graph
• The order of monochromatic subgraphs with a given minimum degree
• scientific article; zbMATH DE number 5904019 (Why is no real title available?)

This page was built for publication: Minimum order of graphs with given coloring parameters

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q488290)