Characterization of $M_3(2)$-graphs

Akbari, S.; Kiani, D.; Mohammadi, F.; Moradi, S.

Abstract

References

Ars Combinatoria

Volume 111
Pages: 505-513

Research article

Characterization of $M_{3} (2)$ -graphs

^¹, ^²,³, ^², ^²

¹Department of Mathematical Sciences Sharif University of Technology P. O. Box 11365-9415, Tehran, Iran.

²Department of Pure Mathematics, Faculty of Mathematics and Computer Sci- ence, Amirkabir University of Technology (Tehran Polytechnic), 424, Hafez Ave., Tehran 15914, Iran.

³Institute for Studies in Theoretical Physics and Mathematics (IPM).

Published: 31/07/2013

Download PDF
Cite

Copyright Link
License

Abstract

A graph $G$ is called an $M_{r} (k)$ -graph if $G$ has no $k$ -list assignment to its vertices with exactly $r$ vertex colorings. We characterize all $M_{3} (2)$ -graphs. More precisely, it is shown that a connected graph $G$ is an $M_{3} (2)$ -graph if and only if each block of $G$ is a complete graph with at least three vertices.

Contents

Ars Combinatoria

Characterization of $M_{3} (2)$ -graphs

Abstract

Information

Guidelines

CP Initiatives

Follow CP

Contents

Ars Combinatoria

Characterization of M3(2)-graphs

Abstract

Information

Guidelines

CP Initiatives

Follow CP

Characterization of $M_{3} (2)$ -graphs