Graph colourings and partitions

DOI10.1016/S0304-3975(00)00231-0MaRDI QIDQ5941502zbMATH OpenFDO

Authors V. Yegnanarayanan

Publication date 20 August 2001

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0304-3975(00)00231-0

zbMATH Keywords

achromatic numberchromatic numberclique numbercolouringsgraphsindependent setpartition graphpartitionsperfect graphspseudoachromatic number

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Review text

The author considers three coloring-related parameters of finite simple undirected graphs: the chromatic, achromatic and pseudochromatic numbers. The chromatic number is the minimum number of colors needed to color the vertices of \(G\) in such a way that adjacent vertices receive different colors. The achromatic number is the maximum size of a partition of the vertices of \(G\) into independent sets so that any two parts are adjacent. The pseudochromatic number is the maximum size of a partition of the vertices of \(G\) so that any two parts are adjacent. NEWLINENEWLINENEWLINEIt is mentioned that the computation of any of the three parameters is NP-complete. These parameters are studied in terms of graph homomorphisms, epimorhisms and graph partitions. A relation fo the achromatic number and projective planes is given, and it is proved that different perfectness-related notions that are defined via the three parameters are equivalent. At last, some bounds are proved for the achromatic and pseudochromatic numbers and the pseudochromatic number of group graph \(G(N_n,D_1)\) is computed.

Recommendations

• The pseudoachromatic number of a graph
• On the existence of graphs with prescribed coloring parameters
• On pseudoachromatic number of graphs
• scientific article; zbMATH DE number 3851129
• A note on pseudocomplete coloring of graphs

Cites work

• Colouring prime distance graphs
• Colouring the real line
• Concerning the achromatic number of graphs
• Distance in graphs
• Edge Dominating Sets in Graphs
• Extremal graphs in some coloring problems
• Further results on the achromatic number
• scientific article; zbMATH DE number 4142077 (Why is no real title available?)
• scientific article; zbMATH DE number 15375 (Why is no real title available?)
• scientific article; zbMATH DE number 3627213 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 3893204 (Why is no real title available?)
• scientific article; zbMATH DE number 3253789 (Why is no real title available?)
• scientific article; zbMATH DE number 3298599 (Why is no real title available?)
• scientific article; zbMATH DE number 3334007 (Why is no real title available?)
• scientific article; zbMATH DE number 3335815 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• scientific article; zbMATH DE number 3097897 (Why is no real title available?)
• Maximum-Minimum Sätze und verallgemeinerte Faktoren von Graphen
• On Complementary Graphs
• ON DISTANCES IN CHROMATIC GRAPHS
• On orthogonal Latin squares
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• On some extremal graph coloring problems of Nordhaus Gaddum class
• On the edge achromatic numbers of complete graphs
• On the existence of graphs with prescribed coloring parameters
• On the pseudoachromatic number of a graph
• On the sum of all distances in a graph or digraph
• Projective Planes
• Reducibility among combinatorial problems
• The achromatic number of a graph
• The complexity of theorem-proving procedures
• The Nonexistence of Certain Finite Projective Planes
• The pseudoachromatic number of a graph

Cited in

(22)

• The diachromatic number of digraphs
• Achromatic number and facial achromatic number of connected locally-connected graphs
• The Hadwiger number, chordal graphs and \(ab\)-perfection
• On the minimum monochromatic or multicolored subgraph partition problems
• Vertex colouring edge partitions
• Fuzzy colouring of fuzzy graphs
• Achromatic numbers for circulant graphs and digraphs
• Geometric achromatic and pseudoachromatic indices
• scientific article; zbMATH DE number 3851129 (Why is no real title available?)
• Colourings, homomorphisms, and partitions of transitive digraphs
• scientific article; zbMATH DE number 4162925 (Why is no real title available?)
• scientific article; zbMATH DE number 5531990 (Why is no real title available?)
• A new characterization of trivially perfect graphs
• STRONG COLORINGS OVER PARTITIONS
• Recent Advances in Constraints
• scientific article; zbMATH DE number 7705706 (Why is no real title available?)
• Achromatic colorings of polarity graphs
• On criticality and additivity of the pseudoachromatic number under join
• On the partition and coloring of a graph by cliques
• Rainbow graph splitting
• Number of distinguishing colorings and partitions
• Vertex partitions of \(r\)-edge-colored graphs

This page was built for publication: Graph colourings and partitions

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