Search

An acyclicedge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic indexof a graph is the minimum number ksuch that there is an acyclic edge coloring using kcolors and is denoted by a′(G). A graph is called 2‐degenerateif any of its induced subgraph has a vertex of degree at most 2. The class of 2‐degenerate graphsproperly contains series–parallel graphs, outerplanar graphs, non− regular subcubic graphs, planar graphs of girth at least6 and circle graphs of girth at least5 as subclasses. It was conjectured by Alon, Sudakov and Zaks (and much earlier by Fiamcik) that a′(G)⩽Δ + 2, where Δ = Δ(G) denotes the maximum degree of the graph. We prove the conjecture for 2‐degenerategraphs. In fact we prove a stronger bound: we prove that if Gis a 2‐degenerate graph with maximum degree Δ, then a′(G)⩽Δ + 1. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:1‐27, 2011

Let G(V, E) be a simple, undirected graph where Vis the set of vertices and Eis the set of edges. A b‐dimensional cube is a Cartesian product I1×I2×···×Ib, where each Iiis a closed interval of unit length on the real line. The cubicityof G, denoted by cub(G), is the minimum positive integer bsuch that the vertices in Gcan be mapped to axis parallel b‐dimensional cubes in such a way that two vertices are adjacent in Gif and only if their assigned cubes intersect. An interval graph is a graph that can be represented as the intersection of intervals on the real line—i.e. the vertices of an interval graph can be mapped to intervals on the real line such that two vertices are adjacent if and only if their corresponding intervals overlap. Suppose S(m) denotes a star graph on m+1 nodes. We define claw numberψ(G) of the graph to be the largest positive integer msuch that S(m) is an induced subgraph of G. It can be easily shown that the cubicity of any graph is at least ⌈log2ψ(G)⌉. In this article, we show that for an interval graph G⌈log2ψ(G)⌉⩽cub(G)⩽⌈log2ψ(G)⌉+2. It is not clear whether the upper bound of ⌈log2ψ(G)⌉+2 is tight: till now we are unable to find any interval graph with cub(G)>⌈log2ψ(G)⌉. We also show that for an interval graph G, cub(G)⩽⌈log2α⌉, where α is the independence number of G. Therefore, in the special case of ψ(G)=α, cub(G) is exactly ⌈log2α2⌉. The concept of cubicity can be generalized by considering boxes instead of cubes. A b‐dimensional box is a Cartesian product I1×I2×···×Ib, where each Iiis a closed interval on the real line. The boxicityof a graph, denoted box(G), is the minimum ksuch that Gis the intersection graph of k‐dimensional boxes. It is clear that box(G)⩽cub(G). From the above result, it follows that for any graph G, cub(G)⩽box(G)⌈log2α⌉. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 323–333, 2010

An acyclicedge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic indexof a graph is the minimum number ksuch that there is an acyclic edge coloring using kcolors and is denoted by a′(G). It was conjectured by Alon, Sudakov and Zaks (and earlier by Fiamcik) that a′(G)⩽Δ+2, where Δ=Δ(G) denotes the maximum degree of the graph. Alon et al. also raised the question whether the complete graphs of even order are the only regular graphs which require Δ+2 colors to be acyclically edge colored. In this article, using a simple counting argument we observe not only that this is not true, but in fact all d‐regular graphs with 2nvertices and d>n, requires at least d+ 2 colors. We also show that a′(Kn, n)⩾n+ 2, when nis odd using a more non‐trivial argument. (Here Kn, ndenotes the complete bipartite graph with nvertices on each side.) This lower bound for Kn, ncan be shown to be tight for some families of complete bipartite graphs and for small values of n. We also infer that for every d, nsuch that d⩾5, n⩾2d+ 3 and dneven, there exist d‐regular graphs which require at least d+2‐colors to be acyclically edge colored. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 226–230, 2010

An acyclicedge coloring of a graph is a proper edge coloring such that there are no bichromatic cycles. The acyclic chromatic indexof a graph is the minimum number ksuch that there is an acyclic edge coloring using kcolors and is denoted by a′(G). It was conjectured by Alon, Sudakov, and Zaks that for any simple and finite graph G, a′(G)⩽Δ + 2, where Δ=Δ(G) denotes the maximum degree of G. We prove the conjecture for connected graphs with Δ(G)⩽4, with the additional restriction that m⩽2n−1, where nis the number of vertices and mis the number of edges in G. Note that for any graph G, m⩽2n, when Δ(G)⩽4. It follows that for any graph Gif Δ(G)⩽4, then a′(G)⩽7. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 192–209, 2009

Your journey through pediatric ECGs continues with the last four principles essential to their analysis, and a review of normal/abnormal findings. [ABSTRACT FROM AUTHOR]

Revised guidelines help evaluate the child who doesn't meet all the classic criteria for KD and provide a framework for long-term management based on the risk of myocardial infarction. [ABSTRACT FROM AUTHOR]

Does supplementing infant formula with long-chain polyunsaturated fatty acids have an effect on visual acuity, growth, and cognitive development? The author examines the evidence. [ABSTRACT FROM AUTHOR]