Search

Abstract: Given a set D of positive integers, the distance graph has vertices all integers Z, and two vertices j and in Z are adjacent if and only if . This paper determines the circular chromatic numbers of some distance graphs. [Copyright &y& Elsevier]

Abstract: The incidence coloring conjecture, or ICC, states that any graph can be incidence-colored with colors, where is the maximum degree of the graph. After being introduced in 1993 by Brualdi and Massey, ICC was shown to be false in general by Guiduli in 1997, following the work of Algor and Alon. However, Shiu, Lam and Chen conjectured that the ICC holds for cubic graphs and proved it for some classes of such graphs. In this paper we prove the ICC for any graph with . [Copyright &y& Elsevier]

Abstract: For a connected graph G, the restricted edge-connectivity is defined as the minimum cardinality of an edge-cut over all edge-cuts S such that each component of contains at least p vertices. In the present paper we introduce the more general parameter defined as the minimum cardinality of an edge-cut over all edge-cuts S such that one component of contains at least p vertices and another component of contains at least q vertices where p and q are positive integers. Analogously, we define as the minimum cardinality of a vertex-cut over all vertex-cuts such that one component of contains at least p vertices and another component of contains at least q vertices. A connected graph G is -connected (-connected), if () is well-defined. First we give useful equivalences to -connectivity and -connectivity and characterize the classes of graphs which are -connected and -connected. Then we prove which generalizes Whitney''s well-known inequality . Finally, we characterize the class of graphs for which is minimum, i.e. and the class of graphs for which is maximum, i.e. or . [Copyright &y& Elsevier]

Abstract: A chordal graph is the intersection graph of a family of subtrees of a host tree. In this paper we generalize this. A graph has an -representation if there exists a host tree T of maximum degree at most h, and a family of subtrees of T, all of maximum degree at most s, such that if and only if . For given , and t, there exist infinitely many forbidden induced subgraphs for the class of -graphs. On the other hand, for fixed , every graph is an -graph provided that we take t large enough. Under certain conditions representations of larger graphs can be obtained from those of smaller ones by amalgamation procedures. Other representability and non-representability results are presented as well. [Copyright &y& Elsevier]

Abstract: For two given graphs and , the Ramsey number is the smallest integer n such that for any graph G of order n, either G contains or the complement of G contains . Let denote a path of order n and a wheel of order . In this paper, we show that for m even and and for m odd and . [Copyright &y& Elsevier]